package com.fosss.recursion;

/**
 * 一维数组表示棋盘
 */
public class Queen8 {
    //理论上用二维数组表示棋盘，实际上那个可以用一维数组解决问题
    //arr[8]={0,4,7,5,2,6,1,3}  数组下标表示第几行（第几个皇后）,arr[i]=val;,val表示第i+1个皇后，放在第i+1行，第val+1列
    int max=8;
    int[] arr=new int[max];
    static int count=0;

    public static void main(String[] args) {

        Queen8 queen8 = new Queen8();
        queen8.check(0);
        System.out.println("一共有"+count+"种解法");
    }


    /**
     * 打印表示8个皇后位置的数组
     */
    private  void print(){
        count++;
        for(int i = 0;i<arr.length; i++){
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }

    /**
     * 判断是否符合规范----不同行，不同列，不在对角线
     * @param n 表示第几个皇后
     * @return 返回是否符合规范
     */
    private boolean judge(int n){
        for(int i = 0;i<n;i++){
            //arr[i]==arr[n]表示同一列，Math.abs((n-i))==Math.abs((arr[n]-arr[i]))表示对角线上
            if(arr[i]==arr[n]||Math.abs((n-i))==Math.abs((arr[n]-arr[i]))){
                return false;
            }
        }
        return true;
    }

    /**
     * @param n 第几个皇后
     */
    public void check(int n){
        if(n==max){
            print();
            return;
        }
        for(int i = 0;i<max;i++){
            //把这个皇后n放到该行的第1列
            arr[n]=i;//n代表第几行,i代表第几列
            if(judge(n)){
                check(n+1);
            }

            //如果冲突，继续执行该循环（i+1）
        }
    }
}












